Typically such a system is programmed to recognise a predetermined set of "valid" character sequences, namely passwords, commands, directory addresses or other identifiers. These valid sequences are .intg.sparse" subsets of the possible sequences that can be generated by the various possible permutations of the characters. A user may input invalid character sequences i.e. which the system does not understand. Hence, the system needs to determine whether or not each input character sequence corresponds to a valid sequence i.e. check that it is one that the system is programmed to recognise.
Optionally and error occurring early in the character string may be reported to the user before the entire character sequence or string has been entered, an obvious exception being password validation. Also, the validation process should be able to accommodate character strings of different lengths.
One form of character sequence validation used in existing systems is explicit matching, in which the entire input sequence (or string), or the part of it input so far, is compared with templates or a look-up table representing valid sequences. A disadvantage of this approach is that an individual template is required for every possible valid sequence and these templates must be searched, which is time consuming. Also, the table or list of templates occupies an inordinate amount of memory space.
Another known form of character sequence validation uses a three-type algorithm. In this system, a series of data records are interconnected by "pointers". Each record contains a valid character in the sequence, and a pointer. The pointer is an address which gives the location of the record corresponding to the next character in the sequence.
Sequences with common leading characters share a common tree nodes near the root of the tree. The tree branches where a succeeding character differs for two or more valid strings. This may be more space efficient than explicit matching, but a minimum of one tree node for each valid sequence is required and the pointers occupy valuable memory space since they must be stored in a record with the data. Also, the central processor has to access a pointer to find each valid character in the string, which takes a significant length of time.